package com.wang.sort3;

import com.wang.sort3.Demo08_GraphGenerator.*;

import java.util.*;

/**
 * @Author: along
 * @Create: 2021/4/23
 * @Description:拓扑排序(有向无环图中)
 */
public class Demo11_TopologySort {
    public static List<Node> sortedTopology(Graph graph) {
        //key:某一个node
        //value:该节点剩余的入度
        HashMap<Node, Integer> inMap = new HashMap<>();
        //剩余入度为0的节点才能进入的队列
        Queue<Node> zeroInQueue = new LinkedList<>();

        for (Node node : graph.nodes.values()
             ) {
            inMap.put(node, node.in);
            if(node.in == 0) {
                zeroInQueue.add(node);
            }
        }
        //拓扑排序的结果，依次加入result
        List<Node> result = new ArrayList<>();
        while (!zeroInQueue.isEmpty()) {
            Node cur = zeroInQueue.poll();
            result.add(cur);
            for (Node next : cur.nexts
                 ) {
                inMap.put(next, inMap.get(next) - 1);
                if(inMap.get(next) == 0) {
                    zeroInQueue.add(next);
                }
            }
        }
        return result;
    }
}
